package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。
 * 
 * 形式上，如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... +
 * A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1]) 就可以将数组三等分。
 * 
 * @author maodou38
 *
 */
public class Solution1013_mime {
	public boolean canThreePartsEqualSum(int[] A) {
			Map numMap=new HashMap<Integer,Object>();//key:和值   value：当前坐标的合集
			int sum=0;
			for(int i=0;i<A.length;i++) {
				sum=sum+A[i];
				if(numMap.get(sum)==null) {
					numMap.put(sum, i);
				}else {
					Object obj = numMap.get(sum);
					if(obj instanceof Integer) {
						List<Integer> distinceList=new ArrayList<Integer>();
						distinceList.add((int)obj);
						distinceList.add(i);
						numMap.put(sum, distinceList);
					}else {//本来就是List<Integer>
						((List<Integer>)obj).add(i);
					}
				}
			}
			if(sum%3!=0) {
				return false;//无法三等分
			}
			int avg=sum/3;//三等分数
			Object onePassThree = numMap.get(avg);
			Object twoPassThree = numMap.get(2*avg);
			if(onePassThree==null||twoPassThree==null) {
				return false;
			}
			if(onePassThree instanceof Integer&&twoPassThree instanceof Integer) {
				if((int)onePassThree< (int)twoPassThree&&(int)twoPassThree!=A.length-1) {
					return true;
				}else {
					return false;
				}
			}else if(onePassThree instanceof List&&twoPassThree instanceof Integer){
				if(((int)((List)onePassThree).get(0))<(int)twoPassThree&&(int)twoPassThree!=A.length-1) {
					return true;
				}else {
					return false;
				}
			}else if(onePassThree instanceof Integer&&twoPassThree instanceof List){
				((List<Integer>)twoPassThree).remove((Object)(A.length-1));
				((List<Integer>)twoPassThree).remove((Object)(onePassThree));
				if(((List<Integer>)twoPassThree).size()!=0&&(int)onePassThree<(int)((List<Integer>)twoPassThree).get(((List<Integer>)twoPassThree).size()-1)) {
					return true;
				}else {
					return false;
				}
			}else {
				((List<Integer>)twoPassThree).remove((Object)(A.length-1));
				((List<Integer>)twoPassThree).remove((Object)(((List<Integer>)onePassThree).get(0)));
				if(((List<Integer>)twoPassThree).size()!=0&&(int)((List<Integer>)onePassThree).get(0)<(int)((List<Integer>)twoPassThree).get(((List<Integer>)twoPassThree).size()-1)) {
					return true;
				}else {
					return false;
				}
			}
	}

	public static void main(String[] args) {
		boolean canThreePartsEqualSum = new Solution1013_mime().canThreePartsEqualSum(new int[] { 6,1,1,13,-1,0,-10,20 });
		System.err.println(canThreePartsEqualSum);
	}
}
